'''
包引入:
* graphviz 绘制树状图
* re 正则匹配
* time (生成时间戳) random(生成随机数) 共同完成不重复的节点编号创建
'''
from graphviz import Digraph
import re
import time
import random

'''
全局量表
  keywords 关键词列表
  *Pat 正则匹配规则
'''
#关键词列表
keywords=['int', 'long', 'short', 'float', 'double', 'char', 'unsigned', 'signed', 'const', 'void', 'volatile', 'enum', 'struct', 'union', 'if', 'else', 'goto', 'switch', 'case', 'do', 'while', 'for', 'continue', 'break', 'return', 'default', 'typedef', 'auto', 'register', 'extern', 'static', 'sizeof'] 
#正则匹配规则
IdPat=re.compile("^[a-zA-z_]\w*") #标识符判定规则 以字母或下划线开头 包含字母 数字 下划线
NumPat=re.compile(r"(^[1-9][0-9]*)|0") #整数判定规则 

'''
函数表
  drawTree(tree) 根据树字典tree 绘制树
  |-getRandId() 生成随机编号
  |-drawTreePoint(tree, dot, parentId, currentId) 根据树字典tree 在句柄对象dot 上绘制节点(currentId)及其与父亲节点的连线(parentId)
  testFullExpr(fullExpr)   对表达式进行初始化后进行检测并返回语法树字典
  |-testExpr(expr)          提取Expr元素返回结果字典
  |-testExpr1(expr)         提取Expr1元素返回结果字典
  |-testTerm(expr)          提取Term元素返回结果字典
  |-testTerm1(expr)         提取Term1元素返回结果字典
  |-testFactor(expr)        提取Factor元素返回结果字典
    |-extractBreaket(expr)  提取()内的元素并返回结果字典
  |-testOp(expr,tid)        提取Op元素返回结果字典
'''

#drawTree()绘制树 并打印
#tree 表示树的字典结构 
def drawTree(tree):
  dot = Digraph(name="Tree", format="png")
  drawTreePoint(tree,dot,-1,getRandId())
  dot.render(filename="Tree")

#getRandId()生成15位的随机节点Id 8位时间戳尾部+7位乱序随机数
def getRandId():
  timeStr= str(int(round(time.time() * 1000)))[-8:]
  randomStr=""
  for i in range(7):
    randomStr+=str(random.randint(1,9))
  return timeStr+randomStr

#drawTreePoint()绘制树节点以及连线
#tree 表示树的字典结构 
#dot  绘图对象  初始传入为None
#parentId 树父亲节点的编号 初代为-1
#currentId 当前节点的编号 时间戳随机ID 唯一性
def drawTreePoint(tree,dot,parentId,currentId):
  if parentId == -1:
      dot.node(currentId,tree["root"])
      drawTreePoint(tree["leafL"],dot,currentId,getRandId())
      drawTreePoint(tree["leafM"],dot,currentId,getRandId())
      drawTreePoint(tree["leafR"], dot,currentId,getRandId())
      return 
  #1.若空节点 不做操作
  if tree is None:
    return
  #2.若是叶子则绘制叶子节点和边
  if isinstance(tree,str):
    dot.node(currentId,tree)
    dot.edge(parentId,currentId)
    return
  #3.若是子树
  if isinstance(tree, dict):
    #3.1若子树根是空的 则跳过该子树
    if tree["root"] is None:
      return
    #3.2若子树有根 则先绘制根节点 并将根节点与父亲节点连线 并递归调用绘制三个子叶  
    else:
      dot.node(currentId,tree["root"])
      dot.edge(parentId,currentId)
      drawTreePoint(tree["leafL"],dot,currentId,getRandId())
      drawTreePoint(tree["leafM"],dot,currentId,getRandId())
      drawTreePoint(tree["leafR"], dot,currentId,getRandId())
      return



#testFullExpr()对表达式进行初始化后进行检测并返回语法树字典
#fullExpr 一个完整的表达式
#返回一棵语法树字典(根据表达式的文法来看 最多三节点) 这也是后续所有树的基本构成
#  {
#     "root":树根的内容(字符串),
#     "leafL":左节点(字符串叶子|子树字典|None)
#     "leafM":中节点(字符串叶子|子树字典|None)
#     "leafR":右节点(字符串叶子|子树字典|None)
#   }
def testFullExpr(fullExpr):
  #1.对输入的表达式先进行去空格初始化 (使用replace将所有空格全部替换)
  fullExpr=fullExpr.replace(" ","").replace("\n","").replace("\t","")
  #2 进行表达式检测
  retDict=testExpr(fullExpr)
  
  if not retDict["status"]:
    #2.1 异常则报错error
    print("Error!")
    return None
  else:
    #2.2 正常则输出检测的表达式与树字典 并返回树字典
    print("解析的表达式为"+retDict["need"])
    print(retDict["needTree"])
    return retDict["needTree"]

#testExpr() 检测并提取Expr元素内容
#expr 表达式字符串
# 返回一个结果字典 
#  {
#     "status":结果状态(0找到|1没找到),
#     "need":返回检测得到的元素 (元素字符串|None),
#     "new":剩下的表达式内容 (表达式字符串|None),
#     "needTree":本次查找后得到的树字典(树字典|None)
#   }
def testExpr(expr):
  needTree={"root":None,"leafL":None,"leafM":None,"leafR":None}
  need=""
  #1.检测Term
  retDict1=testTerm(expr)
  if not retDict1["status"]:
    return {"status":0,"need":None,"new":None}
  else:
    need=need+retDict1["need"]
    needTree["leafL"]=retDict1["needTree"]

  #2.检测Expr1
  retDict2=testExpr1(retDict1["new"])
  if not retDict2["status"]:
    return {"status":0,"need":None,"new":None}
  else:
    need=need+retDict2["need"]
    needTree["leafR"]=retDict2["needTree"]
    if need !="":
      needTree["root"]=need+"  =>Expr"
    return {"status":1,"need":need,"new":retDict2["new"],"needTree":needTree}

#testExpr1() 检测并提取Expr1元素内容
#expr 表达式字符串
# 返回一个结果字典 同上
def testExpr1(expr):
  #print("TestExpr1:"+expr)
  need=""
  needTree={"root":None,"leafL":None,"leafM":None,"leafR":None}
  if expr=="":
    return {"status":1,"need":need,"new":expr,"needTree":needTree}
  #1.检测加减op
  retDitc1=testOp(expr,0)
  if not retDitc1["status"]:
    return {"status":0,"need":None,"new":None} 
  else:
    need=need+retDitc1["need"]
    needTree["leafL"]=retDitc1["needTree"]
  #2.检测Term
  retDict2=testTerm(retDitc1["new"])
  if not retDict2["status"]:
    return {"status":0,"need":None,"new":None} 
  else:
    need=need+retDict2["need"]
    needTree["leafM"]=retDict2["needTree"]
  #3.检测expr1
  retDict3=testExpr1(retDict2["new"])
  if not retDict3["status"]:
    return {"status":0,"need":None,"new":None}
  else:
    need=need+retDict3["need"]
    needTree["leafR"]=retDict3["needTree"]
    if need !="":
      needTree["root"]=need+"  =>Expr1"
    return {"status":1,"need":need,"new":retDict3["new"],"needTree":needTree}

#testTerm() 检测并提取Term元素内容
#expr 表达式字符串
# 返回一个结果字典 同上
def testTerm(expr):
  #print("TestTerm:"+expr)
  need=""
  needTree={"root":None,"leafL":None,"leafM":None,"leafR":None}
  #1.检测Factor
  retDict1=testFactor(expr)
  if not retDict1["status"]:
    return {"status":0,"need":None,"new":None}
  else:
    needTree["leafL"]=retDict1["needTree"]
    need=need+retDict1["need"]
  needTree["leafL"]=retDict1["needTree"]

  #2.检测Term1
  retDict2=testTerm1(retDict1["new"])
  if not retDict2["status"]:
    return {"status":0,"need":None,"new":None}
  else:
    need=need+retDict2["need"]
    needTree["leafR"]=retDict2["needTree"]
    if need !="":
      needTree["root"]=need+"  =>Term"
    return {"status":1,"need":need,"new":retDict2["new"],"needTree":needTree}

#testTerm1() 检测并提取Term1元素内容
#expr 表达式字符串
# 返回一个结果字典 同上
def testTerm1(expr):
  #print("TestTerm1:"+expr)
  need=""
  needTree={"root":None,"leafL":None,"leafM":None,"leafR":None}
  if expr=="":
    return {"status":1,"need":need,"new":expr,"needTree":needTree}

  #1.检测乘除op
  retDict1=testOp(expr, 1)
  if not retDict1["status"]:      #乘除若没匹配则检查加减op
    reDict11=testOp(expr,0)
    if reDict11["status"]:                    #此处若是加减op 则可认为Term1顺利结束
      return {"status":1,"need":need,"new":expr,"needTree":needTree}
    else:
      return {"status":0,"need":None,"new":None}
  else:
    need=need+retDict1["need"]
    needTree["leafL"]=retDict1["needTree"]

  #2.检测Factor
  retDict2=testFactor(retDict1["new"])
  if not retDict2["status"]:
    return {"status":0,"need":None,"new":None}
  else:
    need=need+retDict2["need"]
    needTree["leafM"]=retDict2["needTree"]

  #3.检测Term1
  retDict3=testTerm1(retDict2["new"])
  if not retDict3["status"]:
    return {"status":0,"need":None,"new":None}
  else:
    need=need+retDict3["need"]
    needTree["leafR"]=retDict3["needTree"]
    if need !="":
      needTree["root"]=need+"  =>Term1"
    return {"status":1,"need":need,"new":retDict3["new"],"needTree":needTree}

#testFactor() 检测并提取Factor元素内容
#expr 表达式字符串
# 返回一个结果字典 结构同上 但needTree字段可能为: 字符串(叶节点)|树字典|None
def testFactor(expr):
  #print("TestFactor:"+expr)
  reId=re.match(IdPat,expr)
  reNum=re.match(NumPat, expr)
  #1.检测是否为标识符
  if reId is not None:
    need=reId.group()
    if need not in keywords:
      return {"status":1,"need":need,"new":expr[len(need):],"needTree":need+"  =>Factor_id"}  #标识符
    else:
      return {"status":0,"need":None,"new":None}
  #2.检测是否为数字
  elif reNum is not None:
    need=reNum.group()
    return {"status":1,"need":need,"new":expr[len(need):],"needTree":need+"  =>Factor_Num"}  #数字
  #3.检测是否为带括号的表达式
  else:  
    retDict1=extractBreaket(expr)
    if not retDict1["status"]:
      return {"status":0,"need":None,"new":None}
    
    retDict2=testExpr(retDict1["need"])
    if not retDict2["status"]:
      return {"status":0,"need":None,"new":None}
    else:
      need="("+retDict1["need"]+")"
      needTree={"root":need+"  =>Factor_(expr)","leafL":"(","leafM":retDict2["needTree"],"leafR":")"}
      return {"status":1,"need":need,"new":retDict1["new"],"needTree":needTree}


#extractBreaket() 提取一层括号中的内容
#expr 表达式字符串
# 返回一个结果字典
#  {
#     "status":结果状态(0找到|1没找到),
#     "need":返回括号内的元素(元素字符串|None),
#     "new":返回)后的表达式(表达式字符串|None),
#   }
def extractBreaket(expr):
  count=0
  #1.检测首个是否为(
  if expr[:1] != '(':
    return {"status":0,"need":None,"new":None}
  for index,char in enumerate(expr):
    if char =="(":
      count+=1
    elif char==")":
      count-=1
      if count==0:
        return {"status":1,"need":expr[1:index],"new":expr[index+1:]}
  return {"status":0,"need":None,"new":None}

#testOp() 检测并提取Op元素内容
#expr 表达式字符串
#tid 检测类型 (0检测加减|1检测乘除)
# 返回一个结果字典 结构同上 但needTree字段可能为: 符号字符串(叶节点)|None
def testOp(expr,tid):
  testList=[['+','-'],['*','/']]
  testLabel=["Add","Mul"]
  #检测运算符
  if expr[:1] in testList[tid]:
    need=expr[:1]
    return {"status":1,"need":need,"new":expr[1:],"needTree":need+"  =>"+testLabel[tid]+"Op"}
  else:
    return {"status":0,"need":None,"new":None}


'''
主代码执行区
  输入表达式
  送入检测
  打印树
'''

if __name__ == "__main__":
  fullExpr=input("请输入一段表达式字符(回车确认):")
  MainTree=testFullExpr(fullExpr)
  if MainTree is not None:
    drawTree(MainTree)





